<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            示例 1:
                示例 1：

                输入：nums = [1,2,3], target = 4
                输出：7
                解释：
                所有可能的组合为：
                (1, 1, 1, 1)
                (1, 1, 2)
                (1, 2, 1)
                (1, 3)
                (2, 1, 1)
                (2, 2)
                (3, 1)
                请注意，顺序不同的序列被视作不同的组合。
                示例 2：

                输入：nums = [9], target = 3
                输出：0
        */
            
        /*
            经典递归套路，backTrack(target - nums[i])
            和零钱兑换的区别是，零钱兑换，必须每一层维护一个自己的startIndex，也就是他的顺序是固定的，能有1，3的组合，但是无3，1的组合
        */

        // 问题：map写在哪里,写在最外面
        // 时间复杂度:O(n * t) n是nums的长度，t是target的值
        // 空间复杂度:O(n) memo最多不会存储超过target的值，递归栈的深度也不会超过target的深度
        var combinationSum4 = function(nums, target) {
            const targetMemo = new Map()
            const backTrack = (target) => {
                // 退出条件
                if (target === 0) return 1 // 找到一个方案了
                // map中是否有存在的target => 方案数，可以直接拿来用的
                if (targetMemo.has(target)) return targetMemo.get(target) 
                let res = 0
                for (let i = 0; i < nums.length; i++) {
                    let num = nums[i]
                    // 数字比target大，就return，放不下
                    if (num > target) continue
                    // 这里递归
                    res += backTrack(target - num)
                }
                targetMemo.set(target, res)
                return res
            }
            return backTrack(target)
        }
        console.log(combinationSum4([1, 2, 3], 4));
    </script>
</body>

</html>